package 左哥算法.ch05链表;

import org.junit.Test;

import java.util.*;

public class Ch03相交链表 {

    @Test
    public void test01(){
        int[] arr={1,2,3,4,5};
        int[] arr2={11,12};
        ListNode h1=new ListNode(arr[0]),
                h2=new ListNode(arr2[0]),
                tail1,tail2;
        tail1=h1;
        for (int i=1;i<arr.length;i++) {
            tail1.next=new ListNode(arr[i]);
            tail1=tail1.next;
        }
        tail2=h2;
        for (int i=1;i<arr.length;i++) {
            tail2.next=new ListNode(arr[i]);
            tail2=tail2.next;
        }
    }

    /**
     *题目：
     * 给出两个有环或者无环的链表
     * 判断这两个链表是否相交，如果相交则返回相交节点，不相交则返回null
     *思路：
     * 1.先判断是否有环
     *      判断方式为将节点依次放入Set中，当节点有重复时，第一个重复的节点就是入环节点，无重复则非有环节点
     *      如果一方有环一方无环则不相交
     * 2.无环的情况下，如果相交，则链表终点一定相同，我们可以通过找到两个链表第一个相同节点找到相交节点
     *      找相同节点的方式为:先让两个链表的长度统一，再一起遍历比较
     * 3.有环情况下：
     *      1.判断双方入环节点是否相同
     *      2.如果相同，则一定相交。用无环找相同点的方式找交点，以入环节点为链表终点，
     *      3.如果不同，则让一个入环节点在环中走一圈：
     *          如果碰不到另一个入环节点，则两个链表不相交
     *          如果碰到另一个节点，则两个链表相交，交点为两个入环节点
     */
    public ListNode fun1(ListNode h1,ListNode h2){
        if (h1==null||h2==null){
            return null;
        }
        ListNode r1 = isLoop(h1);   //入环节点1
        ListNode r2 = isLoop(h2);   //入环节点2
        if ((r1!=null)^(r2!=null)){    //一方有环，一方无环
            return null;
        }
        if (r1==null){  //双方无环情况
            ListNode tail1=h1,tail2=h2;
            //找终点
            while (tail1.next!=null){
                tail1=tail1.next;
            }
            while (tail2.next!=null){
                tail2=tail2.next;
            }
            if (tail1==tail2){
                return firstSame(h1,h2,tail1);
            }else {
                return null;
            }
        }
        if (r1==r2){
            return firstSame(h1,h2,r1);
        }
        ListNode start=r1;
        r1=r1.next;
        while (r1!=start){
            if (r1==r2){
                return r1;
            }
            r1=r1.next;
        }
        return null;
    }

    /**
     * 判断是否存在环
     * @return：存在环返回入环节点，不存在返回Null
     */
    public ListNode isLoop(ListNode head){
        Set<ListNode> set = new HashSet<>();
        while (head!=null){
            if (set.contains(head)){
                return head;
            }
            set.add(head);
            head=head.next;
        }
        return null;
    }
    /**
     *获取第一个相同节点
     *思路：
     *  先获取两个的长度，让长链表先走到相同长度
     *  再让两个链表依次比较
     * @param end:两个链表的共同终点
     */
    public ListNode firstSame(ListNode h1,ListNode h2,ListNode end){
        if (h1==null||h2==null||end==null){
            throw new RuntimeException("参数错误");
        }
        int n=0;
        ListNode curr=h1;
        while (curr != end) {
            n++;
            curr=curr.next;
        }
        curr=h2;
        while (curr != end) {
            n--;
            curr=curr.next;
        }
        ListNode lh=n>0?h1:h2;
        ListNode sh=lh==h2?h1:h2;
        n=Math.abs(n);

        while (n>0){    //长链表走到与短链表相同的长度
            n--;
            lh=lh.next;
        }
        while (lh!=end.next){   //包含终点
            if (lh==sh){        //第一个相同点
                return lh;
            }
            lh=lh.next;
            sh=sh.next;
        }
        return null;
    }
}
